package com.lun.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import com.lun.util.BinaryTree.TreeNode;

public class AllPossibleFullBinaryTrees {
	
	//方法一：递归版
    public List<TreeNode> allPossibleFBT(int n) {
        List<TreeNode> result = new ArrayList<>();
        
        if((n & 1) == 0) return result; //偶数的直接返回
        
        if(n == 1) {
        	result.add(new TreeNode(0));
        	return result;
        }
        
        for(int i = 1; i < n; i += 2) {
        	
        	List<TreeNode> lefts = allPossibleFBT(i);
        	List<TreeNode> rights = allPossibleFBT(n - i - 1);
        	
        	for(TreeNode left : lefts) {
        		for(TreeNode right : rights) {
        			TreeNode node = new TreeNode(0);
        			
        			node.left = left;
        			node.right = right;
        			
        			result.add(node);
        		}
        	}
        }	
        return result;
    }
    
    //方法二：迭代版
    public List<TreeNode> allPossibleFBT2(int n) {
        List<TreeNode> result = new ArrayList<>();
        if((n & 1) == 0) return result; //偶数的直接返回

        Map<Integer, List<TreeNode>> cache = new HashMap<>();
        
        cache.put(1, Arrays.asList(new TreeNode(0)));
        
        
        for(int i = 3; i <= n; i += 2) {
        	
        	List<TreeNode> tempList = new ArrayList<>();
        	for(int j = 1; j < i; j += 2) {
        		
        		List<TreeNode> lefts = cache.get(j);
        		List<TreeNode> rights = cache.get(i - j - 1);
        		
        		for(TreeNode left : lefts) {
        			for(TreeNode right : rights) {
        				TreeNode node = new TreeNode(0);
        				
        				node.left = i == n ? clone(left) : left;
        				node.right = i == n ? clone(right) : right;
        				
        				tempList.add(node);
        			}
        		}
        	}
        	if(i == n)
        		return tempList;
        	cache.put(i, tempList);
        }
        
        return cache.get(1);
    }
    
    private TreeNode clone(TreeNode node) {
    	if(node == null) return null;
    	
    	TreeNode newNode = new TreeNode(node.val);
    	
    	newNode.left = clone(node.left);
    	newNode.right = clone(node.right);
    	
    	return newNode;
    }
    
    //下面求出符合题意n个节点二叉树的棵数
    
    public int count(int n) {
    	
    	if((n & 1) == 0) return 0; 
    	
    	if(n == 1) return 1;
    	int result = 0;
    	for(int i = 1; i < n; i += 2) {
    		
    		int l = count(i);
    		int r = count(n - i - 1);
    		
    		
    		result += (l * r);
    	}
    	return result;
    }
    
    public int count2(int n) {    	
    	if((n & 1) == 0) return 0; 
    	
    	Map<Integer, Integer> cache = new TreeMap<>();
    	cache.put(1, 1);

        for(int i = 3; i <= n; i += 2) {
        	int count = 0;
        	for(int j = 1; j < i; j += 2) {
        		
        		int l = cache.get(j);
        		int r = cache.get(i - j - 1);
        		
        		count += (l * r);
        	}
        	cache.put(i, count);
        }
        System.out.println(cache);
    	return cache.get(n);
    }
    
    
}
